大家好,我是毛毛。ヾ(´∀ ˋ)ノ
那就開始今天的解題吧~
Given an array of integers nums
which is sorted in ascending order, and an integer target
, write a function to search target
in nums
. If target
exists, then return its index. Otherwise, return -1
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
nums
are unique.nums
is sorted in ascending order.題目給一個從小到大排的數字list(nums
)與一個數字(target
),要找出target
這個數位於list中的index
,如果都找不到就回傳-1
。
基本上就是如題目意思做Binary Search
。
首先宣告三個變數,mid
、left
和right
:
mid = 0
left = 0
right = len(nums) - 1
接著,就是對半對半的砍,目前right
&left
的中心mid
:
int
,相當於無條件捨去小數點後的數;第二個是兩者相加除以2取商;第三種是我後來看到的,有點像是left
加offset
的感覺。最後,就是看我們的target
比mid
大還是小:
target
小於mid
:代表target
在mid
左邊,所以我們把right
設成mid - 1
。target
大於mid
:代表target
在mid
右邊,所以我們把left
設成mid + 1
。target
等於mid
:代表我們找到啦~就直接回傳mid
的值如果整個跑完都沒有就表示,list找不到target
這個值,就直接回傳-1
。
class Solution:
def search(self, nums: List[int], target: int) -> int:
mid = 0
left = 0
right = len(nums)-1
while left <= right:
mid = int((left + right) / 2)
print(left, mid, right)
if nums[mid] > target:
right = mid -1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1
今天就到這邊啦~
大家明天見